The present invention relates to data processing and, more particularly, to systems for selecting devices for time-sharing resources in a data-processing context. A major objective of the present invention is to optimize time-sharing among devices sharing a common resource.
Much of modern progress is associated with the development of computers. Much of the attraction of computers lies in the myriad of uses to which they can be put. This flexibility is due both to the variety of software that they can run and to the variety of hardware that can be connected to extend a computer""s functionality.
Computer buses provide a common connection standard for hardware devices and a common data pathway that can be time-shared by the devices so that they can communicate with each other and the host system. Typically, bus controllers allocate the data pathway of a bus in response to device requests.
Early buses, e.g., the industry standard bus (ISA), managed the actual communication between devices. However, higher-performance buses permit a suitable device to manage its communications over the bus. In this bus-mastering situation, the bus controller simply selects the device to be the temporary bus master.
As buses become capable of managing more devices, and as more devices become connected to a single bus, the frequency of conflicting requests for bus resources increases. Accordingly, the bus controller must incorporate some system for managing conflicting requests. The following discussion applies most directly to bus-mastering systems in which various devices can present conflicting requests for control of the bus. However, it can be extrapolated to other situations, such as selection of the originating device for a communication, in which one device of many must be selected.
A basic approach to device selection is to rank devices according to some priority scheme and select the device with the highest priority. For example, devices requesting bus control are given a higher priority than buses that are not making such a request. When only one device is requesting control, it can be selected. When two devices are requesting control, priority can be given to the one who has made the request for the longest time, or the one with the highest priority data type to be transferred. (Devices can have requests with different pendencies because the requests can be ignored while another device is completing its turn as bus master.)
Where there are multiple criteria for selecting a device, the criteria themselves must be prioritized. A standard method of expressing this prioritization is to assign each criterion respective bit positions in a numerical priority value. The most important criterion is assigned to the most significant bit positions, and less important criteria are assigned respectively less significant bit positions. When a selection is to be made, the priority values can be input to a xe2x80x9cpriority encoderxe2x80x9d, which simply selects the device associated with the highest priority value.
A typical priority encoder is designed to select a single device even when two or more devices share the highest priority value. In this case, the combinational logic constituting the priority encoder effectively ranks the devices (according to the encoder inputs with which they are associated) and selects the device with the highest ranking among those devices sharing the highest priority. In other words, the device with the highest implicit ranking is selected among those with the highest explicit ranking. Thus, the incorporation of the implicit ranking by the priority encoder ensures that a selection can be made in any situation.
In the course of the present invention, it was determined that the selection scheme implemented by such priority encoders is not, in general, optimal. Since optimizing computer resources is an important performance issue, a more optimal device selection scheme is desired.
Innovation often begins by looking at old things in a new way. To understand the present invention, it is helpful to move from an implementation-specific conceptualization of the device-selection process to a more functional conceptualization. In the latter case, the arbitrary rankings are treated as part of a combined device-specific and arbitrary-ranking priority value. For example, the lowest ranking device can be assigned an arbitrary-ranking value of 0, the next lowest ranking device can be assigned a value of 1, the next lowest ranking device can be assigned a value of 10 (binary notation), and so on to the highest-ranking device.
Adding leading zeroes as necessary (e.g., 000, 001, 010, 011, 100) to achieve equal bit-string lengths for the arbitrary-ranking values, the arbitrary-ranking values can be concatenated to the right of the device-specific priority values conventional input to a priority encode to form the combined priority values. Since the arbitrary rankings are unique, no two devices can have the same combined-priority values. Thus, the combined-priority values allow for unambiguous selection of the highest-priority device.
Each combined-priority value is a concatenation of a device-specific value and an arbitrary-ranking value. Each device-specific value is a function (simple or combinational) of one or more units of data pertaining to the respective device; accordingly, device-specific values can change over time as new device-specific data is received. For example, a device-specific value can change when a device asserts a request for control of a bus. Conventionally, an arbitrary-ranking value is assigned independent of such device-specific data and remains fixed.
In the course of the present invention, and in terms of this conceptualization, it was recognized that the fixed arbitrary rankings biased selection in favor of devices with higher arbitrary-ranking values to the relative exclusion of devices with lower arbitrary-ranking values. It was also recognized that, while the bias might be negligible where priority conflicts are the exception rather than the rule, this bias can be significant where, as is increasing the case, conflicts are the rule rather than the exception. In general, the resulting bias impairs system performance where the excluded device becomes a xe2x80x9cbottleneckxe2x80x9d that slows other devices depending on its contributions.
The present invention provides for variable arbitrary rankings so that the relative time-averaged arbitrary rankings can be controlled. In many cases, they can be controlled to make them more uniform. However, a surprising advantage of the invention is that it permits any desired distribution of time-averaged arbitrary rankings to be implemented. Thus, if it is desired that one device win priority conflicts involving equal device-specific values two-thirds of the time over a second device, this can be arranged by selecting a corresponding scheme for varying arbitrary-ranking values.
The present invention provides for random and pseudo-random selections of arbitrary-ranking values. However, just as it sometimes happens that a randomly tossed coin turns up xe2x80x9cheadsxe2x80x9d 100 times in a row, it can also happen that a device is excluded from selection for an unduly extended time when random selection is used. Accordingly, the present invention also provides various round-robin schemes for varying arbitrary-ranking values that reduce the likelihood of such anomalies.
In the case of the round-robin schemes, the changes in arbitrary rankings can be determined as a function of the device that is selected. In such a case, the selected device (which is presumably taking its turn in controlling a bus) can be assigned a lowest arbitrary ranking (to favor devices that have not been serviced for a while). In this case, an arbitrary ranking can be determined in part, but not completely, by device-specific data for the respective device. Alternatively, the round robin can be derived independently of the selections. In the latter case, the round robin can function as a pseudo-random ranking generator.
To minimize the time a device must wait before selection, the arbitrary rankings can be updated at least half as frequently as the device selection is changed. Where the arbitrary rankings are changed as a function of the device selection, the device-selection and ranking-update frequencies are substantially equal. Where the arbitrary rankings are changed independently, it is preferable that they are changed more frequently than the device selections.
The inventions thus provides for a novel priority encoder in which, in effect, the arbitrary rankings are varied over time. The invention also can be used in conjunction with a conventional priority encoder by adding a variable most-significant arbitrary-ranking bit position to the least significant ends of the priority values input to the priority encoder. The single-bit values can be controlled to effect changes in arbitrary ranking.
As indicated above, the bias imposed by the arbitrary rankings can be controlled, minimized, or even eliminated by proper selection of the values involved in the selection scheme. In fact, if these values are programmable, then the bias can be programmed to match the current constellation of devices attached to the bus and/or to the current software running on the host system.
It should also be noted that while the invention is described primarily in the context of computer buses, it applies as well to other situations in which one device is to be selected on some priority basis. For example, as detailed below, it can be used to select the cache location to which fetched data is to be written.
A major advantage of the invention is that it allows the bias associated with arbitrary rankings to be minimized, selected, or even controlled, as desired, to optimize overall system performance. The invention can be implemented by manipulating a single bit per device appended to the respective device priority value. These and other features and advantages of the invention are apparent from the description below with reference to the following drawings.